package arithmetic.demo12;

import java.security.KeyPair;
import java.util.*;


/**
 * 题目： 栈_字符串解码
 */
class Solution {
    public String decodeString(String s) {
        int n = s.length();
        char[] chs = s.toCharArray();
        // 定义字符串栈和 数字栈
        Stack<String> strStack = new Stack<>(); Stack<Integer> intStack = new Stack<>();
        
        // 先添加一个空串， 防止栈越界
        strStack.push("");

        int i =0;
        while(i<n) {
            if(chs[i] == '[') {
                // 左括号
                i++;
                // 统计字符串
                StringBuilder tmp = new StringBuilder();
                while(i < n && chs[i]  >= 'a' && chs[i] <= 'z') {
                    tmp.append(chs[i]);
                    i++;
                }

                // 加入字符串栈
                strStack.push(tmp.toString());

            } else if( chs[i] >= '0' &&  chs[i] <= '9') {
                // 数字栈
                // 统计数字
                int num = chs[i] - '0';
                i++;
                while(chs[i] >= '0' && chs[i] <= '9') {
                    num = (num * 10) + (chs[i] - '0');
                    i++;
                }

                // 加入到数字栈中
                intStack.push(num);

            } else if(chs[i] == ']'){
                // 出栈并加入
                int count = intStack.pop();
                String s1 = strStack.pop() ;
                StringBuilder tmp = new StringBuilder();

                // 解码过程
                while(count-- > 0) {
                    tmp.append(s1);
                }

                // 加入到栈顶字符串的后面
                String cur = strStack.pop();
                cur += tmp.toString();

                // 最后回到栈顶
                strStack.push(cur);
                i++;
                
            } else {
                // 无数字的字符串
                
                // 先提取字符串
                // 统计字符串
                StringBuilder tmp = new StringBuilder();
                while(i < n && chs[i]  >= 'a' && chs[i] <= 'z') {
                    tmp.append(chs[i]);
                    i++;
                }


                // 加入到栈顶字符串的后面
                String cur = strStack.pop();
                cur += tmp.toString();

                // 最后回到栈顶
                strStack.push(cur);
            }

        }


        return strStack.pop();
    }
}


//class Test {
//    public static void main(String[] args) {
//        Solution solution= new Solution();
//        System.out.println(solution.decodeString("3[a]2[bc]"));
//    }
//}


/**
 * 题目： 栈_验证栈序列
 */


class Solution2 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int cur = 0, dest = 0;
        stack.push(-1);
        while (cur < pushed.length) {
            // 在未遇到相同的元素进行入栈
            while(cur < pushed.length && pushed[cur] != popped[dest]) {
                stack.push(pushed[cur]);
                cur++;
            }

            // 相同后两边同时向右走
            cur++;
            dest++;


            // 观察栈顶元素是否是当前需要弹出的元素
            while(dest < popped.length && popped[dest] == stack.peek()) {
                stack.pop();
                dest++;
            }
        }

        // 如果栈为空就说明弹出成功
        return stack.size() == 1;
    }
}


/**
 * 题目： 队列_n叉树的层序遍历
 */


// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};




class Solution3 {
    // 定义一个全局来存储
    List<List<Integer>> ret ;
    public List<List<Integer>> levelOrder(Node root) {
        // 初始化
        ret  = new ArrayList<>();
        dfs(root , 0 );

        return ret;
    }

    public void  dfs(Node root, int pos) {
        // 递归出口
        if(root == null) {
            return;
        }

        // 检查该层是否出现过
        // 如果没有出现就 创建一层
        if(pos  == ret.size()) {
            ret.add(new ArrayList<>());
        }


        // 添加元素
        ret.get(pos).add(root.val);

        // 遍历 n 叉树
        List<Node> children = root.children;
        for(int i=0; i < children.size() ; i++) {
            dfs(children.get(i), pos+1);
        }


    }
}


/**
 * 题目： 宽搜_N叉树的层序遍历
 */





class Solution4 {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        // 队列存储
        Queue<Node> queue = new LinkedList<>();
        // 先添加元素
        queue.add(root);

        // 用队列模拟宽搜
        while(!queue.isEmpty()) {
            // 外层出队列
            int sz = queue.size();
            List<Integer> tmp = new ArrayList<>();
            // 统计本层的节点信息
            for(int i =0; i < sz; i++) {
                // 内层加入
                Node node = queue.poll();
                tmp.add(node.val);

                // for(Node cur : node.children) {
                //     if(cur != null) {
                //         queue.add(cur);
                //     }
                // }
            }

            // 最终把这一层返回
            ret.add(tmp);
        }

        return ret;
    }


}




class TreeNode {
      int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

/**
 * 题目： 队列_栈_二叉树锯齿形层序遍历
 */


class Solution5 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        int count = 0;
        List<List<Integer>>  ret = new ArrayList<>();

        // 如果节点为 null 就直接返回
        if(root == null) return ret;

        // 队列存储
        Queue<TreeNode> queue = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            // 先得到该层的节点
            int sz = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                // 得到该节点
                stack.push(queue.poll());
            }

            for(int i = 0; i < sz ; i++) {

                TreeNode node = stack.pop();
                list.add(node.val);

                // 分情况进入队列
                if(count % 2 == 0) {
                    // 得到左节点
                    if(node.left != null) {
                        queue.add(node.left);
                    }
                    // 得到右字节
                    if(node.right != null) {
                        queue.add(node.right);
                    }
                } else {
                    // 得到右节点
                    if(node.right != null) {
                        queue.add(node.right);
                    }
                    // 得到左字节
                    if(node.left != null) {
                        queue.add(node.left);
                    }
                }
            }

            count++;
            // 把该层记录进结果
            ret.add(list);
        }


        return ret;
    }


}





/**
 * 题目: 队列_逆序_二叉树锯齿形层序遍历
 */

class Solution6 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        int count = 1;
        List<List<Integer>>  ret = new ArrayList<>();

        // 如果节点为 null 就直接返回
        if(root == null) return ret;

        // 队列存储
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            // 先得到该层的节点
            int sz = queue.size();
            List<Integer> list = new ArrayList<>();


            for(int i = 0; i < sz ; i++) {

                TreeNode node = queue.poll();
                list.add(node.val);
                // 得到左节点
                if(node.left != null) {
                    queue.add(node.left);
                }
                // 得到右字节
                if(node.right != null) {
                    queue.add(node.right);
                }

            }

            // 如果该层是偶数层就逆序
            if(count % 2 == 0) Collections.reverse(list);

            count++;

            // 把该层记录进结果
            ret.add(list);
        }


        return ret;
    }


}


/**
 * 题目：  队列_二叉树的最大宽度
 */


class Solution8 {
    public int widthOfBinaryTree(TreeNode root) {
        int ret = Integer.MIN_VALUE;
        Queue<TreeNode> queue = new LinkedList<>();
        //    特殊情况
        if(root.left == null && root.right == null) {
            return 1;
        }

        queue.add(root);
        int len = 1;

        // 宽搜
        while( len != 0) {
            int sz = queue.size();
            len = 0;
            // 处理当前节点 并记录长度
            for(int i  = 0; i < sz; i++) {
                TreeNode node = queue.poll();
                // 如果当前节点为 null
                if(node == null) {
                    queue.add(null); queue.add(null);
                } else {
                    // 更新长度
                    len = i + 1;
                    // 入栈孩子节点
                    //  null 节点也加入
                    queue.add(node.left);
                    queue.add(node.right);
                }

            }



            // 更新结果
            ret = Math.max(ret, len);
        }


        Map.Entry<TreeNode, Integer> entry=   Map.entry(new TreeNode(),  10);
        return ret;
    }
}




class Solution7 {
    public int widthOfBinaryTree(TreeNode root) {


        int ret = Integer.MIN_VALUE;
        Queue<Map.Entry<TreeNode, Integer>> queue = new LinkedList<>();
        // 特殊情况
        if(root.left == null && root.right == null) {
            return 1;
        }


        queue.add(Map.entry(root, 1));
        int len = 1;


        // 宽搜
        while(!queue.isEmpty()) {
            int sz = queue.size();
            // 处理当前节点 并记录长度
            int bagin =  0 , end = 0;
            for(int i  = 0; i < sz; i++) {
                // 得到键值对
                Map.Entry<TreeNode, Integer> entry = queue.poll();
                TreeNode node = entry.getKey();
                int index =  entry.getValue();

                // 记录队头元素和队尾的下标
                if(i == 0) {
                    bagin = index;
                }
                if(i == sz-1) {
                    end = index;
                }

                // 计算孩子节点的下标 并加入队列中
                if(node.left != null) {
                    queue.add(Map.entry(node.left, 2* index));
                }
                if(node.right != null) {
                    queue.add(Map.entry(node.right,2* index + 1));
                }

            }


            // 更新结果
            ret = Math.max(ret, end - bagin + 1);
        }


        return ret;
    }


}



//class Test1 {
//    public static void main(String[] args) {
//        Solution7 solution7 = new Solution7();
//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//
//
//        System.out.println(solution7.widthOfBinaryTree(root));
//    }
//
//}


